/*
题目: 网格图中递增路径的数目
给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/
 */
public class CountPaths {
    private static final int mod = (int) (1e9 + 7);
    private int[] dir = new int[] {0, -1, 0, 1, 0};
    int row, col;
    int[][] memo = null;

    public int countPaths(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        // 以 grid[row][col] 为起点的递增路径数量
        memo = new int[row][col];

        // 以每个点为起点
        int src = 0;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                src += searchPath(grid, i, j) + 1;
                src %= mod;
            }
        }

        return src;
    }

    private int searchPath(int[][] grid, int x, int y) {
        if (memo[x][y] != 0) {
            return memo[x][y];
        }

        int src = 0;
        for (int i = 0; i < 4; i ++) {
            int nextX = x + dir[i];
            int nextY = y + dir[i + 1];

            if (nextX >= 0 && nextY >= 0 && nextX < row && nextY < col && grid[x][y] < grid[nextX][nextY]) {
                src += searchPath(grid, nextX, nextY) + 1;
                src %= mod;
            }
        }

        return memo[x][y] = src;
    }
}
